The ability to detect motion that may have occurred between subsequent frames, or images, in a video of a scene is useful in applications such as machine vision, motion compensation, and data compression. The most popular methods of motion detection and estimation utilize a "block matching" method.
In a block matching method, a first image of a scene (i.e., a reference image) and a second image (i.e., a test image) are segmented into N.times.M blocks. Each block is comprised of pixels. Corresponding blocks from the reference image and the test image are compared mathematically using some matching method. Corresponding pixels in corresponding blocks are called pixel pairs. Popular matching methods presently being used include a "mean of the absolute differences" (MAD) method and a "mean squared error" (MSE) method. MAD computes the sum of the absolute value of the difference of each pixel pair of the corresponding blocks in order to generate a score. MSE computes the sum of the square of the difference of each pixel pair of the corresponding blocks.
If little motion occurs between the reference image and the test image then the pixel pairs will cancel when differenced in both MAD and MSE and a low score will result. If sufficient motion has occurred then the pixel pair won't cancel and a high score will result. The score is then compared to a threshold to determine whether or not motion has occurred between the reference image and the test image.
If no motion has occurred between the reference image and the test image then the test image is discarded and a new test image is acquired. The steps described above are then repeated using the new test image in order to determine if motion has occurred between the reference image and the new test image.
If motion has occurred between the reference image and the test image then such motion is indicated, the reference image is discarded, the test image becomes the new reference image, a new test image is acquired, and the steps described above are repeated using the new reference image and the new test image to determine whether or not motion has occurred between the new reference image and the new test image.
MAD and MSE are easily implemented, but tend to perform badly when gaussian noise is present in two images that should not otherwise indicate that any motion has occurred. Gaussian noise occurs frequently in sonograms and radar images. One reason why MAD and MSE may falsely indicate motion when there isn't any if gaussian noise is present in the images is that gaussian noise in the reference frame may not be related at all to gaussian noise in the test image. So, the two gaussian noise images may not cancel when differenced. Gaussian noise minus gaussian noise results in gaussian noise. If two images should not indicate any motion but contain gaussian noise then MAD and MSE will assign a high score to the gaussian noise result instead of assigning a low score as expected.
Other prior art matching methods include cross-correlation and the Radon Transform. These methods perform better than MAD and MSE in the presence of gaussian noise, but falsely indicate motion in the presence of strong gaussian noise which commonly occurs in sonograms or radar images.
U.S. Pat. No. 3,641,257, entitled "NOISE SUPPRESSOR FOR SURVEILLANCE AND INTRUSION-DETECTING SYSTEM," discloses a correlation method for dealing with noise in a surveillance and intrusion detection system. Correlation is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images (i.e., strong gaussian noise). U.S. Pat. No. 3,641,257 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 4,894,716, entitled "T.V. MOTION DETECTOR WITH FALSE ALARM IMMUNITY," discloses the use of a low-pass filter and, mainly, a phase-detector to guard against noise-induced false detection of motion. Phase detection is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 4,894,716 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,111,511, entitled "IMAGE MOTION VECTOR DETECTING APPARATUS," discloses the use of both a low-pass filter and a high-pass filter to guard against noise-induced false detection of motion. Using just a low-pass filter and a high-pass filter is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,111,511 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,157,732, entitled "MOTION VECTOR DETECTOR EMPLOYING IMAGE SUBREGIONS AND MEDIAN VALUES," discloses the use of a median filter to guard against noise-induced false detection of motion. Median filtering by itself is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,157,732 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,365,603, entitled "METHOD FOR ANALYZING MOVEMENTS IN TEMPORAL SEQUENCES OF DIGITAL IMAGES," discloses the use of a time-recursive filter to guard against noise-induced false detection of motion. Using just a time-recursive filter is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,365,603 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,535,302, entitled "METHOD AND APPARATUS FOR DETERMINING IMAGE AFFINE FLOW USING ARTIFICIAL NEURAL SYSTEM WITH SIMPLE CELLS AND LIE GERMS," discloses the use of least square error fitting circuit based on a Lie group model to guard against noise-induced false detection of motion. Using just this matching method is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,535,302 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,543,858, entitled "METHOD OF AND APPARATUS FOR REDUCING NOISE IN A MOTION DETECTOR SIGNAL," discloses the use of recursive filtering (or low-pass filtering) to guard against noise-induced false detection of motion. Using just recursive filtering is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,543,858 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,548,659, entitled "METHOD AND APPARATUS FOR DETECTING CHANGES IN DYNAMIC IMAGES," discloses the use of a noise model based on the input images and the difference of the input images to guard against noise-induced false detection of motion. Such a noise model is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images because gaussian noise does not cancel upon differencing with different gaussian noise but results in gaussian noise that may induce a false detection of motion. U.S. Pat. No. 5,548,659 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,586,202, entitled "MOTION DETECTING APPARATUS," does not address noise-induced false detection of motion, and is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,586,202 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,588,067, entitled "MOTION DETECTION AND IMAGE ACQUISITION APPARATUS AND METHOD OF DETECTING THE MOTION OF AND ACQUIRING AN IMAGE OF AN OBJECT," discloses the use of a correlation function to guard against noise-induced false detection of motion. A correlation function is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,588,067 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,589,884, entitled "ADAPTIVE QUANTIZATION CONTROLLED BY SCENE CHANGE DETECTION," does not address noise-induced false detection of motion and is, therefore, insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,589,884 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,600,731, entitled "METHOD FOR TEMPORALLY ADAPTIVE FILTERING OF FRAMES OF A NOISY IMAGE SEQUENCE USING MOTION ESTIMATION," discloses the use of linear minimum mean square error matching to guard against noise-induced false detection of motion. Using such a matching method is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,600,731 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,627,586, entitled "MOVING BODY DETECTION DEVICE OF CAMERA," does not address noise-induced false detection of motion and is, therefore, insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images. U.S. Pat. No. 5,627,586 is hereby incorporated by reference into the specification of the present invention.
In an article entitled "High Speed High Accuracy Motion Detection and Tracking on the Parallel Pipelined Projection Engine," published in New York, N.Y. by the IEEE on Sep. 6, 1989 in The Sixth Multidimensional Signal Processing Workshop, page 242, W. B. Baringer and R. W. Brodersen disclose the use of the Radon transform to reduce video noise. The Radon transform is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images.
In an article entitled "Array Architecture for Block Matching Algorithms," published in New York, N.Y. by the IEEE in 1989, pages 1301-1308, Thomas Komarek and Peter Pirsch disclose the use of the "mean of the absolute differences" (MAD) in a block matching algorithm. MAD is insufficient to guard against noise-induced false detection of motion in the presence of gaussian noise that is commonly found in sonograms or radar images.